/*
动态规划求解：
dp[i]为i节台阶的上楼方法数

由于每次只能上一级或两级
递推式:
dp[i] = dp[i-1] + dp[i-2]

初始情形:
dp[1] = 1
dp[2] = 2

*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int climbStairs(int n)
    {
        if (n == 1)
            return 1;
        else if (n == 2)
            return 2;
        int dp[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];

        return dp[n];
    }
};

int main(int argc, char const* argv[])
{
    Solution temp;
    cout << temp.climbStairs(5) << endl;
    return 0;
}